package com.leetcode.contest;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/30 22:48
 */
public class LC5899两个最好的不重叠活动 {

    public static int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int[] nextMaxValue = new int[events.length + 1];
        for (int i = events.length - 1; i >= 0; i--) {
            nextMaxValue[i] = Math.max(events[i][2], nextMaxValue[i + 1]);
        }
        int answer = 0;
        for (int[] event : events) {
            //二分搜索找到当前活动结束时间之后的下一个最大价值的活动
            int nextEventIndex = binarySearch(events, event[1]);
            int sum = event[2] + nextMaxValue[nextEventIndex];
            answer = Math.max(answer, sum);
        }
        return answer;
    }

    private static int binarySearch(int[][] events, int endTime) {
        int left = 0, right = events.length;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (events[mid][0] <= endTime) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
//        int[][] events = {{1, 3, 2}, {4, 5, 2}, {2, 4, 3}};
//        int[][] events = {{1, 3, 2}, {4, 5, 2}, {1, 5, 5}};
        int[][] events = {{66, 97, 90}, {98, 98, 68}, {38, 49, 63}, {91, 100, 42}, {92, 100, 22}, {1, 77, 50}, {64, 72, 97}};
        System.out.println(maxTwoEvents(events));
    }
}
